//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 示例: 
//
// 输入: [-2,1,-3,4,-1,2,1,-5,4]
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 
//
// 进阶: 
//
// 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 
// Related Topics 数组 分治算法 动态规划 
// 👍 2396 👎 0


package leetcode.editor.cn;

import java.util.HashMap;

//Java：最大子序和
public class P53MaximumSubarray{
    public static void main(String[] args) {
        Solution solution = new P53MaximumSubarray().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//暴力法
/*class Solution {
    public int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                res = Math.max(res,sum);
            }
        }
        return  res;
    }
}*/
    //动态规划
/*    class Solution {
        public int maxSubArray(int[] nums) {
            int len = nums.length;
            if (len == 0) {
                return 0;
            }
            int pre = nums[0];
            int res = pre;
            for (int i = 1; i < len; i++) {
                pre = Math.max(nums[i],pre+nums[i]);
                res = Math.max(pre,res);
            }
            return res;
        }
    }*/
    //分治
    class Solution {

        public int maxSubArray(int[] nums) {
            int len = nums.length;
            if (len == 0) {
                return 0;
            }
            return maxSubArraySum(nums, 0, len - 1);
        }

        private int maxCrossingSum(int[] nums, int left, int mid, int right) {
            // 一定会包含 nums[mid] 这个元素
            int sum = 0;
            int leftSum = Integer.MIN_VALUE;
            // 左半边包含 nums[mid] 元素，最多可以到什么地方
            // 走到最边界，看看最值是什么
            // 计算以 mid 结尾的最大的子数组的和
            for (int i = mid; i >= left; i--) {
                sum += nums[i];
                if (sum > leftSum) {
                    leftSum = sum;
                }
            }
            sum = 0;
            int rightSum = Integer.MIN_VALUE;
            // 右半边不包含 nums[mid] 元素，最多可以到什么地方
            // 计算以 mid+1 开始的最大的子数组的和
            for (int i = mid + 1; i <= right; i++) {
                sum += nums[i];
                if (sum > rightSum) {
                    rightSum = sum;
                }
            }
            return leftSum + rightSum;
        }

        private int maxSubArraySum(int[] nums, int left, int right) {
            if (left == right) {
                return nums[left];
            }
            int mid = (left + right) /2 ;
            return max3(maxSubArraySum(nums, left, mid),
                    maxSubArraySum(nums, mid + 1, right),
                    maxCrossingSum(nums, left, mid, right));
        }

        private int max3(int num1, int num2, int num3) {
            return Math.max(num1, Math.max(num2, num3));
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

    }